package myself.a009BinaryTree;

/**
 * @author 叶之越
 * Description
 * Date 2021/1/27
 * Time 15:04
 * Mail 739153436@qq.com
 */
public class SuccessorNode {
    public static Node getSuccessorNode(Node node) {
        if (node == null) {
            return null;
        }
        // 如果有右子树，那么后继节点肯定存在
        if (node.right != null) {
            node = node.right;
            while (node.left != null) {
                node = node.left;
            }
            return node;
        }
        // 不存在右子树，那么当前节点就时某颗树上的最右节点，其后继
        // 节点是找到x节点是哪一个节点左树上的最右即可，或者为null
        Node parent = null;
        while (node.parent != null) {
            parent = node.parent;
            if (parent.left == node) {
                return parent;
            }
            node = parent;
        }
        return null;
    }

    public static class Node {
        public int value;
        public Node left;
        public Node right;
        public Node parent;

        public Node(int data) {
            this.value = data;
        }
    }
}
